package 力扣.栈;

import java.util.Deque;
import java.util.LinkedList;

public class 数组中元素左边离我最近且比我大的元素的位置 {
    public static void main(String[] args) {
        DoubleCheck(new int[] { 5, 4 });
        DoubleCheck(new int[] { 1, 2, 4, 9, 4, 0, 5 });

        RandomCheck();
//        System.out.println();

    }
    private static int findLeftLarge(int[] A, int i) {
        for (int j = i - 1; j >= 0; j--) {
            if (A[j] > A[i]) {
                return j;
            }
        }
        return -1;
    }

    private static void check(int[] A, int[] ans) {
        if (A == null || A.length == 0) {
            return;
        }

        final int N = A.length;
        for (int i = 0; i < N; i++) {
            final int r = ans[i];
            if (r != findLeftLarge(A, i)) {
                System.out.println("ERROR");
            }
        }
    }

    public static void DoubleCheck(int[] A) {
        int[] ans = findLeftLarge(A);
        check(A, ans);
    }

    private static int NextInt() {
        final double d = Math.random();
        final int i = (int) (d * 1000);
        return i;
    }

    public static void RandomCheck() {
        for (int i = 0; i < 100; i++) {
            final int len = NextInt() + 1;
            int[] A = new int[len];
            for (int j = 0; j < len; j++) {
                A[j] = NextInt();
            }

            DoubleCheck(A);
        }
    }


    //左边：遍历的方向需要改变
    //左边比我大：使用递减栈
    public static int[] findLeftLarge2(int[] A) {
        Deque<Integer> stack = new LinkedList<>();
        int[] ans = new int[A.length];
        for (int i = A.length - 1; i >= 0 ; i--) {
            while (!stack.isEmpty() && A[stack.peek()] < A[i]){//出栈
                ans[stack.poll()] = i;
            }
            stack.push(i);//入栈
        }
        while (!stack.isEmpty()){
            ans[stack.poll()] = -1;
        }
        return ans;
    }
//方法二：从左到右遍历：递减栈
    public static int[] findLeftLarge(int[] A) {
        Deque<Integer> stack = new LinkedList<>();
        int[] ans = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            while (!stack.isEmpty() && A[stack.peek()] <= A[i]){
                stack.poll();
            }
            if (!stack.isEmpty()){
                ans[i] = stack.peek();
            }else {
                ans[i] = -1;
            }
            stack.push(i);
        }
        return ans;
    }

}
